#include "isort.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <assert.h>

typedef uint32_t data_t;

/* Function prototypes */

inline static void merge_f(data_t * __restrict A, int p, int q, int r, data_t * __restrict left);
inline static void copy_f(data_t * __restrict source, data_t * __restrict dest, int n) ;
static void sort_f_helper(data_t * __restrict A, int p, int r, data_t * left) ;
inline static void mem_alloc(data_t ** space, int size) ;
inline static void mem_free(data_t ** space) ;

/* Function definitions */

/* Basic merge sort */
void sort_f(data_t * __restrict A, int p, int r) 
{
	assert (A) ; 

	if (p < r && p >=0 && r >=0 && A) 
	{
		int q = (p+r)/2 ;
		data_t * left = 0;
		mem_alloc(&left, q-p+2) ;
		sort_f_helper(A, p, r, left) ;
		mem_free(&left) ;
	}
}	

static void sort_f_helper(data_t * __restrict A, int p, int r, data_t * left)
{
        assert (A) ;
        if (p < r-20)
	{
	  int q = (p+r)/2 ;
	  sort_f_helper(A, p, q, left);
	  sort_f_helper(A, q + 1, r, left);
	  merge_f(A, p, q, r, left) ;
	}	
	else if (p < r)
	{
	  isort(A+p, A+r) ;
	}
}

/* A merge routine. Merges the sub-arrays A [p..q] and A [q + 1..r].
 * Uses two arrays 'left' and 'right' in the merge operation.
 */
inline static void merge_f(data_t * __restrict A, int p, int q, int r, data_t * __restrict left) 
{ 
	assert(A) ;
	assert(p <= q) ;
	assert((q + 1) <= r) ;
	int n = q - p + 1;

        if (n+1 <= 0 || r-q+1 <= 0)
        {
	  return ;
        }
	
	copy_f (&(A [p]), left, n) ; 
	left [n] = UINT_MAX ;

	int i = 0 ;
      	int j = q-p ;
	int k = p ;
	A += p ;
	for ( ; k <= r ; k++)
	{
	  long cmp = (* (left+i) <= * (A+j)) ;
	  long min = * (A+j) ^ ((*(A+j) ^ *(left+i)) & -cmp) ;
	  * A++ = min ;
	  i += cmp ;
	  j -= cmp ;
	}
}

inline static void copy_f(data_t * __restrict source, data_t * __restrict dest, int n)                              
{                                                                             
        assert (dest) ;                                                       
        assert (source) ;                                                     
        int i ;                                                               
        for (i = 0 ; i < n ; i++)                                            
	{
	  * dest++ = * source++ ;
	}                                                                     
}

inline static void mem_alloc(data_t ** space, int size)
{
  *space = (data_t *) malloc(sizeof(data_t) * size) ;
  if (*space == NULL)
    {
      printf("out of memory...\n") ;
    }
}

inline static void mem_free(data_t ** space)
{
  free(*space) ;
  *space = 0 ;
}
